home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / DDJBSP2.ZIP / BSPMAKER / BSPMAKER.CPP next >
Encoding:
C/C++ Source or Header  |  1995-07-24  |  51.1 KB  |  1,572 lines
  1. /*  bspmaker.cpp
  2.  
  3.     Win32 2D BSP tree editor and compiler.
  4.     Tested with VC++ 2.0 running under Windows NT 3.5. */
  5.  
  6. #include <windows.h>
  7. #include <windowsx.h>
  8. #include <commdlg.h>
  9. #include <stdio.h>
  10. #include <malloc.h>
  11. #include <math.h>
  12. #include "bspmaker.hpp"
  13.  
  14. #define DBG 0       // set to 1 for debug checking
  15.  
  16. #define MAX_NUM_VERTICES    1000
  17. #define MAX_NUM_LINESEGS    1000
  18. #define MAX_PATH_LENGTH     256
  19. #define NO_CHILD_TREE     -1    // value for front or back tree index if there is
  20.                             //  no tree in that direction
  21. #define MAX_INT            0x7FFFFFFF
  22. #define MIN_INT         0x80000000
  23. #define MATCH_TOLERANCE 0.00001
  24.  
  25. // A vertex
  26. typedef struct _VERTEX
  27. {
  28.    double x;
  29.    double y;
  30. } VERTEX;
  31.  
  32. // A potentially split piece of a line segment, as processed from the
  33. // base line in the original list
  34. typedef struct _LINESEG
  35. {
  36.    _LINESEG *pnextlineseg;
  37.     int startvertex;
  38.     int endvertex;
  39.     double walltop;
  40.     double wallbottom;
  41.     double tstart;
  42.     double tend;
  43.     int color;
  44.     _LINESEG *pfronttree;
  45.     _LINESEG *pbacktree;
  46. } LINESEG, *PLINESEG;
  47.  
  48. static char szAppName[]="BSPMAKER";
  49. static HWND hwndApp;
  50. static int  Compiling = FALSE;
  51. static int Width, Height;
  52. static LINESEG *plineseglist;
  53. static int numlinesegs;
  54. static LINESEG *pCompiledLinesegs;
  55. static int NumCompiledLinesegs = 0;
  56. static VERTEX *pvertexlist;
  57. static int numvertices, realnumvertices;
  58. static HINSTANCE hInstApp;
  59. static HDC hdcDraw = NULL;
  60. static HBITMAP hbmDraw = NULL;
  61. static HBITMAP hbmOld = NULL;
  62. static int lineListMinX, lineListMaxX;
  63. static int lineListMinY, lineListMaxY;
  64. static int VisibleCompile;
  65. static int DoStep = TRUE;
  66. static int SingleStep = 0;
  67. static int ExitProgram = FALSE;
  68. static int HaltCompile = FALSE;
  69. static int ClipTopLeftVertex, ClipTopRightVertex;
  70. static int ClipBottomLeftVertex, ClipBottomRightVertex;
  71.  
  72. void DrawAllSplitters(LINESEG * pCurrentSplitter, LINESEG * pTree);
  73. void DrawBSPClippedLine(LINESEG *pSplit, LINESEG *pCurrentTree);
  74. void DisplayTree(LINESEG * pCurrentNode);
  75. int ShowSingleStepTree(LINESEG * pLinesegsToPartition,
  76.     LINESEG * pSplit, LINESEG * pCurrentTree);
  77. void CompileBSPTree(void);
  78. void CleanUpObjects(void);
  79. void DisplayMessageBox(char * text);
  80. int LoadLineFile(void);
  81. int SaveLineFile(void);
  82. int WriteNode(LINESEG * ptree, LINESEG * ptreebase);
  83. LRESULT CALLBACK AppWndProc(HWND hwnd, UINT msg, WPARAM wParam,
  84.     LPARAM lParam);
  85. void AppPaint(HWND hwnd, HDC hdc);
  86. LINESEG * SelectBSPTree(LINESEG * plineseghead,
  87.     LINESEG * pCurrentTree, LINESEG ** pParentsChildPointer);
  88. LINESEG * BuildBSPTree(LINESEG * plineseghead, LINESEG * proot,
  89.     LINESEG * pCurrentTree);
  90. #if DBG
  91. void CheckForBacklinks(LINESEG *plineseg);
  92. #define CHECK_FOR_BACKLINKS(x)    CheckForBacklinks(x)
  93. #else
  94. #define CHECK_FOR_BACKLINKS(x)
  95. #endif    //DBG
  96.  
  97.  
  98. /////////////////////////////////////////////////////////////////////
  99. // Load time initialization.
  100. /////////////////////////////////////////////////////////////////////
  101.  
  102. int LoadInit(HINSTANCE hInst,HINSTANCE hPrev,int sw,LPSTR szCmdLine)
  103. {
  104.     WNDCLASS cls;
  105.  
  106.     pvertexlist = (VERTEX *)calloc(MAX_NUM_VERTICES, sizeof(VERTEX));
  107.     if (pvertexlist == NULL) {
  108.         DisplayMessageBox("Couldn't get vertex storage memory");
  109.         return FALSE;
  110.     }
  111.  
  112.     plineseglist = (LINESEG *)calloc(MAX_NUM_LINESEGS,
  113.                                      sizeof(LINESEG));
  114.     if (plineseglist == NULL) {
  115.         DisplayMessageBox("Couldn't get line segment storage memory");
  116.         return FALSE;
  117.     }
  118.  
  119.     pCompiledLinesegs = (LINESEG *)calloc(MAX_NUM_LINESEGS,
  120.                                           sizeof(LINESEG));
  121.     if (pCompiledLinesegs == NULL) {
  122.         DisplayMessageBox("Couldn't get compiled line segment storage");
  123.         return FALSE;
  124.     }
  125.  
  126. if (!hPrev) {
  127.         cls.hCursor        = LoadCursor(0, IDC_ARROW);
  128.         cls.hIcon          = 0;
  129.         cls.lpszMenuName   = "AppMenu";
  130.         cls.lpszClassName  = szAppName;
  131.         cls.hbrBackground  = (HBRUSH)GetStockObject(WHITE_BRUSH);
  132.         cls.hInstance      = hInst;
  133.         cls.style          = CS_BYTEALIGNCLIENT | CS_VREDRAW |
  134.                              CS_HREDRAW;
  135.         cls.lpfnWndProc    = (WNDPROC)AppWndProc;
  136.         cls.cbClsExtra     = 0;
  137.         cls.cbWndExtra     = 0;
  138.         if (!RegisterClass(&cls))
  139.             return FALSE;
  140.     }
  141.  
  142.     hwndApp = CreateWindow (szAppName, szAppName,
  143.             WS_OVERLAPPEDWINDOW,
  144.             CW_USEDEFAULT, 0, 350,350, 0, 0, hInst, 0);
  145.     HDC hdc = GetDC(hwndApp);
  146.     if ((hdcDraw = CreateCompatibleDC(hdc)) == NULL) {
  147.         DisplayMessageBox("Couldn't create compatible DC");
  148.         return FALSE;
  149.     }
  150.     ReleaseDC(hwndApp, hdc);
  151.  
  152.     ShowWindow(hwndApp, sw);
  153.  
  154.     return TRUE;
  155. }
  156.  
  157.  
  158. /////////////////////////////////////////////////////////////////////
  159. // Main proc and message pump.
  160. /////////////////////////////////////////////////////////////////////
  161.  
  162. int CALLBACK WinMain(HINSTANCE hInst,HINSTANCE hPrev,LPSTR szCmdLine,
  163.     int sw)
  164. {
  165.     MSG msg;
  166.  
  167.     hInstApp = hInst;
  168.  
  169.     if (!LoadInit(hInst, hPrev, sw, szCmdLine)) // initialize the app
  170.         return FALSE;
  171.  
  172.     // Pump messages until quitting time, letting the idle proc
  173.     // draw, if possible, when there's nothing else to do.
  174.     for (;;) {
  175.         if (PeekMessage(&msg, 0, 0, 0, PM_REMOVE)) {
  176.             if (msg.message == WM_QUIT)
  177.                 break;
  178.             TranslateMessage(&msg);
  179.             DispatchMessage(&msg);
  180.             WaitMessage();
  181.         }
  182.     }
  183.     return msg.wParam;
  184. }
  185.  
  186.  
  187. /////////////////////////////////////////////////////////////////////
  188. // Draws the current state of the world on the screen.
  189. /////////////////////////////////////////////////////////////////////
  190.  
  191. void AppPaint(HWND hwnd, HDC hdc)
  192. {
  193.     POINT pt;
  194.     SIZE size;
  195.     HPEN hpen;
  196.     static int x = 0;
  197.  
  198.     SetMapMode(hdcDraw, MM_TEXT);
  199.     PatBlt(hdcDraw, 0, 0, Width, Height, WHITENESS);
  200.  
  201.     SetMapMode(hdcDraw, MM_ANISOTROPIC);    
  202.     SetWindowExtEx(hdcDraw, lineListMaxX - lineListMinX + 1,
  203.                  (lineListMaxY - lineListMinY + 1), &size);
  204.     SetViewportExtEx(hdcDraw, Width*9/10, -Height*9/10, &size);
  205.     SetViewportOrgEx(hdcDraw, Width/20, Height*19/20, &pt);
  206.     SetWindowOrgEx(hdcDraw, lineListMinX, lineListMinY, &pt);
  207.  
  208.     hpen = GetStockObject(BLACK_PEN);
  209.     hpen = SelectObject(hdcDraw, hpen);
  210.  
  211.     double StartX, StartY, EndX, EndY;
  212.     LINESEG *pTemp = plineseglist;
  213.     for (int i=0; i < numlinesegs; i++, pTemp++) {
  214.  
  215.         StartX = pvertexlist[pTemp->startvertex].x;
  216.         StartY = pvertexlist[pTemp->startvertex].y;
  217.         EndX = pvertexlist[pTemp->endvertex].x;
  218.         EndY = pvertexlist[pTemp->endvertex].y;
  219.  
  220.         MoveToEx(hdcDraw,
  221.           (int)floor(StartX + (EndX - StartX) * pTemp->tstart + 0.5),
  222.           (int)floor(StartY + (EndY - StartY) * pTemp->tstart + 0.5),
  223.           &pt);
  224.         LineTo(hdcDraw,
  225.           (int)floor(StartX + (EndX - StartX) * pTemp->tend + 0.5),
  226.           (int)floor(StartY + (EndY - StartY) * pTemp->tend + 0.5));
  227.     }
  228.  
  229.     SetWindowExtEx(hdcDraw, Width, Height, &size);
  230.     SetViewportExtEx(hdcDraw, Width, Height, &size);
  231.     SetViewportOrgEx(hdcDraw, 0, 0, &pt);
  232.     SetWindowOrgEx(hdcDraw, 0, 0, &pt);
  233.     SetMapMode(hdcDraw, MM_TEXT);    
  234.  
  235.     hpen = SelectObject(hdcDraw, hpen);
  236.     DeleteObject(hpen);
  237.  
  238.     BitBlt(hdc, 0, 0, Width, Height, hdcDraw, 0, 0, SRCCOPY);
  239.     
  240.     GdiFlush(); // make sure this gets drawn right away
  241. }
  242.  
  243.  
  244. /////////////////////////////////////////////////////////////////////
  245. // Main window proc. Receives all messages.
  246. /////////////////////////////////////////////////////////////////////
  247.  
  248. LRESULT CALLBACK AppWndProc(HWND hwnd, UINT msg, WPARAM wParam,
  249.     LPARAM lParam)
  250. {
  251.     PAINTSTRUCT ps;
  252.     HDC hdc;
  253.     
  254.     switch (msg) {
  255.         case WM_CREATE: 
  256.             break;
  257.  
  258.         case WM_COMMAND:
  259.             switch(wParam) {
  260.                 case IDM_EXIT:
  261.                     PostMessage(hwnd, WM_CLOSE, 0, 0L);
  262.                     break;
  263.  
  264.                 case IDM_LOAD:
  265.                     if (!LoadLineFile()) {
  266.                         CleanUpObjects();
  267.                         PostQuitMessage(0);
  268.                     } else {
  269.                         hdc = GetDC(hwnd);
  270.                         AppPaint(hwnd, hdc);
  271.                         ReleaseDC(hwnd, hdc);
  272.                     }
  273.                     break;
  274.  
  275.                 case IDM_SAVE:
  276.                     SaveLineFile();
  277.                     break;
  278.  
  279.                 case IDM_COMPILE:
  280.                     VisibleCompile = 0;
  281.                     CompileBSPTree();
  282.                     break;
  283.  
  284.                 case IDM_VISIBLE_COMPILE:
  285.                     VisibleCompile = 1;
  286.                     CompileBSPTree();
  287.                     break;
  288.  
  289.                 case IDM_SINGLE_STEP_COMPILE:
  290.                     VisibleCompile = 1;
  291.                     SingleStep = 1;
  292.                     CompileBSPTree();
  293.                     SingleStep = 0;
  294.                     break;
  295.  
  296.                 case IDM_HALT_COMPILE:
  297.                     HaltCompile = TRUE;
  298.                     break;
  299.             }
  300.             return 0L;
  301.  
  302.         case WM_DESTROY:        // clean up before leaving
  303.             if (!Compiling) {
  304.                 CleanUpObjects();
  305.                 PostQuitMessage(0);
  306.             } else {
  307.                 HaltCompile = TRUE;
  308.                 ExitProgram = TRUE;
  309.             }
  310.             break;
  311.  
  312.         case WM_CHAR:
  313.             if (SingleStep) {
  314.                 // In single-step mode, a keystroke lets the next
  315.                 // step happen
  316.                 DoStep = TRUE;
  317.             }
  318.             break;
  319.  
  320.         case WM_PAINT:
  321.             hdc = BeginPaint(hwnd, &ps);
  322.             AppPaint (hwnd, hdc);
  323.             EndPaint(hwnd,&ps);
  324.             return 0L;
  325.  
  326.         case WM_SIZE:
  327.             RECT rect;
  328.             GetClientRect(hwnd, &rect);
  329.             Width = rect.right;
  330.             Height = rect.bottom;
  331.  
  332.             // Create a new compatible bitmap into which to draw
  333.             hdc = BeginPaint(hwnd, &ps);
  334.             HBITMAP hbm = CreateCompatibleBitmap(hdc,
  335.                                                  Width, Height);
  336.             EndPaint(hwnd,&ps);
  337.  
  338.             if (!hbm) {
  339.                 CleanUpObjects();   // failed; fatal error
  340.                 PostQuitMessage(0);
  341.             } else {
  342.                 hbmDraw = hbm;
  343.                 if (!hbmOld) {
  344.                     // First time; remember the original bitmap
  345.                     hbmOld = SelectObject(hdcDraw, hbm);
  346.                 } else {
  347.                     // Not first time; replace the old with the new
  348.                     hbm = SelectObject(hdcDraw, hbm);
  349.                     DeleteObject(hbm);
  350.                 }
  351.             }
  352.             break;
  353.     }
  354.     return DefWindowProc(hwnd,msg,wParam,lParam);
  355. }
  356.  
  357.  
  358. /////////////////////////////////////////////////////////////////////
  359. // Destroys the objects we have lying around.
  360. /////////////////////////////////////////////////////////////////////
  361.  
  362. void CleanUpObjects()
  363. {
  364.     if (hbmOld) {
  365.         SelectObject(hdcDraw, hbmOld);
  366.         DeleteObject(hbmDraw);
  367.     }
  368.     DeleteObject(hdcDraw);
  369. }
  370.  
  371.  
  372. /////////////////////////////////////////////////////////////////////
  373. // Loads a line file, replacing the current line set.
  374. // Puts up a message box and returns FALSE for fatal errors; returns
  375. // TRUE for success in loading, or if the user cancels. Zero-length
  376. // line and vertex lists may be returned.
  377. /////////////////////////////////////////////////////////////////////
  378.  
  379. int LoadLineFile()
  380. {
  381.     OPENFILENAME ofn;
  382.     char szFile[MAX_PATH_LENGTH], szFileTitle[256];
  383.     int i, cbString;
  384.     char chReplace;
  385.     char  szFilter[256];
  386.     FILE *infile;
  387.  
  388.     if (LoadString(hInstApp, IDS_INITLINEFILESTRING,
  389.             szFile, sizeof(szFile)) == 0) {
  390.         DisplayMessageBox("Init line file name load error");
  391.         return FALSE;
  392.     }
  393.  
  394.     if ((cbString = LoadString(hInstApp, IDS_LINEFILEFILTERSTRING,
  395.             szFilter, sizeof(szFilter))) == 0) {
  396.         DisplayMessageBox("Line file filter load error");
  397.         return FALSE;
  398.     }
  399.  
  400.     chReplace = szFilter[cbString - 1]; // retrieve wild character
  401.     for (i = 0; szFilter[i] != '\0'; i++) {
  402.         if (szFilter[i] == chReplace)
  403.             szFilter[i] = '\0';
  404.     }
  405.  
  406.     memset(&ofn, 0, sizeof(OPENFILENAME));
  407.     ofn.lStructSize = sizeof(OPENFILENAME);
  408.     ofn.hwndOwner = hwndApp;
  409.     ofn.lpstrFilter = szFilter;
  410.     ofn.nFilterIndex = 1;
  411.     ofn.lpstrFile = szFile;
  412.     ofn.nMaxFile = sizeof(szFile);
  413.     ofn.lpstrFileTitle = szFileTitle;
  414.     ofn.nMaxFileTitle = sizeof(szFileTitle);
  415.     ofn.lpstrInitialDir = NULL;
  416.     ofn.Flags = OFN_PATHMUSTEXIST | OFN_FILEMUSTEXIST;
  417.  
  418. TryAgain:
  419.     if (GetOpenFileName(&ofn)) {
  420.         //Open the file
  421.         infile = fopen(ofn.lpstrFile, "r");
  422.         if (infile == NULL) {
  423.             DisplayMessageBox("Failed to open input line file");
  424.             goto TryAgain;
  425.         }
  426.  
  427.         // Read the vertex list in
  428.         numvertices = 0;
  429.         lineListMinX = lineListMinY = MAX_INT;
  430.         lineListMaxX = lineListMaxY = MIN_INT;
  431.         while ((fscanf(infile, "%lg,%lg,",
  432.                 &pvertexlist[numvertices].x, 
  433.                 &pvertexlist[numvertices].y) != EOF) &&
  434.                 (pvertexlist[numvertices].x != MAX_INT)) {
  435.  
  436.             if (pvertexlist[numvertices].x < (double)lineListMinX) {
  437.                 lineListMinX = (int)floor(pvertexlist[numvertices].x);
  438.             }
  439.  
  440.             if (pvertexlist[numvertices].x > (double)lineListMaxX) {
  441.                 lineListMaxX = (int)ceil(pvertexlist[numvertices].x);
  442.             }
  443.  
  444.             if (pvertexlist[numvertices].y < (double)lineListMinY) {
  445.                 lineListMinY = (int)floor(pvertexlist[numvertices].y);
  446.             }
  447.  
  448.             if (pvertexlist[numvertices].y > (double)lineListMaxY) {
  449.                 lineListMaxY = (int)ceil(pvertexlist[numvertices].y);
  450.             }
  451.  
  452.             if (++numvertices >= MAX_NUM_VERTICES) {
  453.                 DisplayMessageBox("Too many vertices; emptying list");
  454.                 numvertices = 0;
  455.                 numlinesegs = 0;
  456.                 fclose(infile);
  457.                 goto TryAgain;
  458.             }
  459.         }
  460.  
  461.         if (numvertices == 0) {
  462.             DisplayMessageBox("Vertex list is empty");
  463.             numlinesegs = 0;
  464.             fclose(infile);
  465.             goto TryAgain;
  466.         }
  467.  
  468.         realnumvertices = numvertices;
  469.  
  470.         // Do the four maximum-extent vertices
  471.         ClipTopLeftVertex = numvertices;
  472.         pvertexlist[ClipTopLeftVertex].x =
  473.                 (double)lineListMinX -
  474.                 (double)abs(lineListMinX - lineListMaxX) * 0.05;
  475.         pvertexlist[ClipTopLeftVertex].y =
  476.                 (double)lineListMinY -
  477.                 (double)abs(lineListMinY - lineListMaxY) * 0.05;
  478.         if (++numvertices >= MAX_NUM_VERTICES) {
  479.             DisplayMessageBox("Too many vertices; emptying list");
  480.             numvertices = realnumvertices = 0;
  481.             numlinesegs = 0;
  482.             fclose(infile);
  483.             goto TryAgain;
  484.         }
  485.  
  486.         ClipTopRightVertex = numvertices;
  487.         pvertexlist[ClipTopRightVertex].x =
  488.                 (double)lineListMaxX +
  489.                 (double)abs(lineListMinX - lineListMaxX) * 0.05;
  490.         pvertexlist[ClipTopRightVertex].y =
  491.                 (double)lineListMinY -
  492.                 (double)abs(lineListMinY - lineListMaxY) * 0.05;
  493.         if (++numvertices >= MAX_NUM_VERTICES) {
  494.             DisplayMessageBox("Too many vertices; emptying list");
  495.             numvertices = realnumvertices = 0;
  496.             numlinesegs = 0;
  497.             fclose(infile);
  498.             goto TryAgain;
  499.         }
  500.  
  501.         ClipBottomLeftVertex = numvertices;
  502.         pvertexlist[ClipBottomLeftVertex].x =
  503.                 (double)lineListMinX -
  504.                 (double)abs(lineListMinX - lineListMaxX) * 0.05;
  505.         pvertexlist[ClipBottomLeftVertex].y =
  506.                 (double)lineListMaxY +
  507.                 (double)abs(lineListMinY - lineListMaxY) * 0.05;
  508.         if (++numvertices >= MAX_NUM_VERTICES) {
  509.             DisplayMessageBox("Too many vertices; emptying list");
  510.             numvertices = realnumvertices = 0;
  511.             numlinesegs = 0;
  512.             fclose(infile);
  513.             goto TryAgain;
  514.         }
  515.  
  516.         ClipBottomRightVertex = numvertices;
  517.         pvertexlist[ClipBottomRightVertex].x =
  518.                 (double)lineListMaxX +
  519.                 (double)abs(lineListMinX - lineListMaxX) * 0.05;
  520.         pvertexlist[ClipBottomRightVertex].y =
  521.                 (double)lineListMaxY +
  522.                 (double)abs(lineListMinY - lineListMaxY) * 0.05;
  523.         if (++numvertices >= MAX_NUM_VERTICES) {
  524.             DisplayMessageBox("Too many vertices; emptying list");
  525.             numvertices = realnumvertices = 0;
  526.             numlinesegs = 0;
  527.             fclose(infile);
  528.             goto TryAgain;
  529.         }
  530.  
  531.         // Read the initial line segment list in (a line segment is a
  532.         // pair of vertices and a pair of t values)
  533.         numlinesegs = 0;
  534.         while ((fscanf(infile, "%d,%d, %lg,%lg, %d",
  535.                 &plineseglist[numlinesegs].startvertex,
  536.                 &plineseglist[numlinesegs].endvertex,
  537.                 &plineseglist[numlinesegs].walltop,
  538.                 &plineseglist[numlinesegs].wallbottom,
  539.                 &plineseglist[numlinesegs].color) != EOF) &&
  540.                 (plineseglist[numlinesegs].startvertex != MAX_INT)) {
  541.  
  542.             plineseglist[numlinesegs].pnextlineseg =
  543.                     &plineseglist[numlinesegs+1];
  544.             plineseglist[numlinesegs].tstart = 0.0;
  545.             plineseglist[numlinesegs].tend = 1.0;
  546.  
  547.             if (++numlinesegs >= MAX_NUM_LINESEGS) {
  548.                 DisplayMessageBox("Too many linesegs; emptying list");
  549.                 fclose(infile);
  550.                 numvertices = 0;
  551.                 numlinesegs = 0;
  552.                 goto TryAgain;
  553.             }
  554.         }
  555.  
  556.         if (numlinesegs == 0) {
  557.             DisplayMessageBox("Lineseg list is empty");
  558.             numvertices = 0;
  559.             fclose(infile);
  560.             goto TryAgain;
  561.         }
  562.  
  563.         // Mark the end of the line segment linked list
  564.         plineseglist[numlinesegs-1].pnextlineseg = NULL;
  565.  
  566.         fclose(infile); // we're done with the line file
  567.     }
  568.     return TRUE;
  569. }
  570.  
  571.  
  572. /////////////////////////////////////////////////////////////////////
  573. // Saves the current compiled BSP tree.
  574. // Puts up a message box and returns FALSE for fatal errors or if
  575. // the user cancels; returns TRUE for success in loading.
  576. /////////////////////////////////////////////////////////////////////
  577.  
  578. int SaveLineFile()
  579. {
  580.     OPENFILENAME ofn;
  581.     char szFile[MAX_PATH_LENGTH], szFileTitle[256];
  582.     FILE *outfile;
  583.     int i, cbString;
  584.     char chReplace;
  585.     char  szFilter[256];
  586.  
  587.     if (LoadString(hInstApp, IDS_INITBSPFILESTRING,
  588.             szFile, sizeof(szFile)) == 0) {
  589.         DisplayMessageBox("Init BSP file name load error");
  590.         return FALSE;
  591.     }
  592.  
  593.     chReplace = szFilter[cbString - 1]; // retrieve wild character
  594.     for (i = 0; szFilter[i] != '\0'; i++) {
  595.         if (szFilter[i] == chReplace)
  596.             szFilter[i] = '\0';
  597.     }
  598.  
  599.  
  600.     memset(&ofn, 0, sizeof(OPENFILENAME));
  601.     ofn.lStructSize = sizeof(OPENFILENAME);
  602.     ofn.hwndOwner = hwndApp;
  603.     ofn.lpstrFilter = NULL;
  604.     ofn.nFilterIndex = 0;
  605.     ofn.lpstrFile = szFile;
  606.     ofn.nMaxFile = sizeof(szFile);
  607.     ofn.lpstrFileTitle = szFileTitle;
  608.     ofn.nMaxFileTitle = sizeof(szFileTitle);
  609.     ofn.lpstrInitialDir = NULL;
  610.     ofn.Flags = OFN_PATHMUSTEXIST;
  611.  
  612.     if (GetSaveFileName(&ofn)) {
  613.         // Open the file
  614.         outfile = fopen(ofn.lpstrFile, "w");
  615.         if (outfile == NULL) {
  616.             DisplayMessageBox("Failed to open output BSP file");
  617.             return(FALSE);
  618.         }
  619.  
  620.         //
  621.         // Write out the header
  622.         //
  623.         fprintf(outfile, "2D BSP Tree Version, %d\n", VERSION);
  624.  
  625.         //
  626.         // Write out the # of vertices and the vertex list, shifted left 16 bits
  627.         // so we end up in 16.16 fixed point. Skip the extra vertices for
  628.         // the bounding rectangle
  629.         //
  630.         fprintf(outfile, "------------------------------\n");
  631.         fprintf(outfile, "Vertices section\n");
  632.         fprintf(outfile, "------------------------------\n");
  633.         fprintf(outfile, "# vertices:, %d\n", realnumvertices);
  634.  
  635.         for (i=0; i<realnumvertices; i++)
  636.         {
  637.             fprintf(outfile, "%ld,%ld\n",
  638.                     (long) (pvertexlist[i].x * (double)0x10000 + 0.5),
  639.                     (long) (pvertexlist[i].y * (double)0x10000 + 0.5));
  640.         }
  641.  
  642.         //
  643.         // Write out the # of nodes and the nodes
  644.         //
  645.         fprintf(outfile, "------------------------------\n");
  646.         fprintf(outfile, "Nodes section\n");
  647.         fprintf(outfile, "------------------------------\n");
  648.         fprintf(outfile, "# nodes:, %d\n", NumCompiledLinesegs);
  649.  
  650.         for (i=0; i<NumCompiledLinesegs; i++)
  651.         {
  652.                fprintf(outfile, "%d,%d, %ld,%ld, %ld,%ld, %d,%d, %d\n",
  653.                     pCompiledLinesegs[i].startvertex,
  654.                     pCompiledLinesegs[i].endvertex,
  655.                     (long) (pCompiledLinesegs[i].walltop * (double)0x10000 + 0.5),
  656.                        (long) (pCompiledLinesegs[i].wallbottom * (double)0x10000 + 0.5),
  657.                        (long) (pCompiledLinesegs[i].tstart * (double)0x10000 + 0.5),
  658.                        (long) (pCompiledLinesegs[i].tend * (double)0x10000 + 0.5),
  659.                     pCompiledLinesegs[i].pfronttree ? pCompiledLinesegs[i].pfronttree - pCompiledLinesegs : NO_CHILD_TREE,
  660.                     pCompiledLinesegs[i].pbacktree ? pCompiledLinesegs[i].pbacktree - pCompiledLinesegs : NO_CHILD_TREE,
  661.                        pCompiledLinesegs[i].color);
  662.            }
  663.  
  664.         fprintf(outfile, "------------------------------\n");
  665.         fprintf(outfile, "End of file\n");
  666.           fprintf(outfile, "------------------------------\n");
  667.  
  668.         fclose(outfile); // we're done with the line file
  669.     }
  670.  
  671.     return FALSE;
  672. }
  673.  
  674.  
  675. /////////////////////////////////////////////////////////////////////
  676. // Displays a message box.
  677. /////////////////////////////////////////////////////////////////////
  678.  
  679. void DisplayMessageBox(char *text)
  680. {
  681.     static char *title = "";
  682.  
  683.     MessageBox(hwndApp, text, title, MB_OK);
  684. }
  685.  
  686.  
  687. /////////////////////////////////////////////////////////////////////
  688. // Compiles the current line segment list into a BSP tree.
  689. /////////////////////////////////////////////////////////////////////
  690.  
  691. void CompileBSPTree()
  692. {
  693.     LINESEG *pCompiledTree;
  694.     LINESEG *pTemp;
  695.     LINESEG ClipTop, ClipBottom, ClipLeft, ClipRight;
  696.  
  697.     if (numlinesegs == 0) {
  698.         DisplayMessageBox("Nothing to compile");
  699.         return;
  700.     }
  701.  
  702.     // Copy the lineseg list to the compile buffer, so we don't
  703.     // mess up the original data
  704.     memcpy(pCompiledLinesegs, plineseglist,
  705.            MAX_NUM_LINESEGS * sizeof(LINESEG));
  706.  
  707.     // Fix up all pointers except the NULL pointer at the end to
  708.     // point into the compiled list instead of the original list.
  709.     // Conveniently, the linesegs are always loaded in sequential
  710.     // order and each just points to the next
  711.     pTemp = pCompiledLinesegs;
  712.     while (pTemp->pnextlineseg) {
  713.         pTemp->pnextlineseg =
  714.                 (LINESEG *)((int)pTemp->pnextlineseg +
  715.                 (int)pCompiledLinesegs - (int)plineseglist);
  716.         pTemp++;
  717.     }
  718.  
  719.     // Make the initial tree the four clipping limits
  720.     ClipTop.tstart = 0.0;
  721.     ClipTop.tend = 1.0;
  722.     ClipTop.startvertex = ClipTopRightVertex;
  723.     ClipTop.endvertex = ClipTopLeftVertex;
  724.     ClipTop.pfronttree = &ClipBottom;
  725.     ClipTop.pbacktree = NULL;
  726.  
  727.     ClipBottom.tstart = 0.0;
  728.     ClipBottom.tend = 1.0;
  729.     ClipBottom.startvertex = ClipBottomLeftVertex;
  730.     ClipBottom.endvertex = ClipBottomRightVertex;
  731.     ClipBottom.pfronttree = &ClipLeft;
  732.     ClipBottom.pbacktree = NULL;
  733.  
  734.     ClipLeft.tstart = 0.0;
  735.     ClipLeft.tend = 1.0;
  736.     ClipLeft.startvertex = ClipTopLeftVertex;
  737.     ClipLeft.endvertex = ClipBottomLeftVertex;
  738.     ClipLeft.pfronttree = &ClipRight;
  739.     ClipLeft.pbacktree = NULL;
  740.  
  741.     ClipRight.tstart = 0.0;
  742.     ClipRight.tend = 1.00;
  743.     ClipRight.startvertex = ClipBottomRightVertex;
  744.     ClipRight.endvertex = ClipTopRightVertex;
  745.     ClipRight.pfronttree = NULL;
  746.     ClipRight.pbacktree = NULL;
  747.  
  748.     NumCompiledLinesegs = numlinesegs;
  749.  
  750.     Compiling = TRUE;
  751.  
  752.     // Gray out menu items we don't want activated during compiles,
  753.     // and activate the compile-specific ones
  754.     EnableMenuItem(GetMenu (hwndApp), IDM_LOAD, MF_GRAYED);
  755.     EnableMenuItem(GetMenu (hwndApp), IDM_COMPILE, MF_GRAYED);
  756.     EnableMenuItem(GetMenu (hwndApp), IDM_VISIBLE_COMPILE, MF_GRAYED);
  757.     EnableMenuItem(GetMenu (hwndApp), IDM_SINGLE_STEP_COMPILE,
  758.                    MF_GRAYED);
  759.     EnableMenuItem(GetMenu (hwndApp), IDM_HALT_COMPILE,
  760.                    MF_ENABLED);
  761.     EnableMenuItem(GetMenu (hwndApp), IDM_SAVE, MF_GRAYED);
  762.  
  763.     // Build the BSP tree
  764.     if ((pCompiledTree = SelectBSPTree(pCompiledLinesegs, &ClipTop,
  765.                                        &ClipRight.pfronttree)) ==
  766.             NULL) {
  767.         if (ExitProgram) {
  768.             CleanUpObjects();
  769.             PostQuitMessage(0);
  770.         } else if (HaltCompile) {
  771.             DisplayMessageBox("Compile halted by user");
  772.             HaltCompile = FALSE;   // reset for next time
  773.         } else {
  774.             DisplayMessageBox("Compile halted due to error");
  775.         }
  776.  
  777.     } else {
  778.  
  779.         // If the root node isn't the first node in the node array,
  780.         // swap the root node and the first node and all pointers
  781.         // to the first node (nothing points to the root node) so
  782.         // the root node becomes the first node, so when this tree
  783.         // gets loaded by another program, they know the first node
  784.         // is the root
  785.         if (pCompiledTree != pCompiledLinesegs) {
  786.             for (int i=0; i<NumCompiledLinesegs; i++) {
  787.                 if (pCompiledLinesegs[i].pfronttree ==
  788.                             pCompiledLinesegs) {
  789.                     pCompiledLinesegs[i].pfronttree = pCompiledTree;
  790.                 }
  791.  
  792.                 if (pCompiledLinesegs[i].pbacktree ==
  793.                             pCompiledLinesegs) {
  794.                     pCompiledLinesegs[i].pbacktree = pCompiledTree;
  795.                 }
  796.             }
  797.  
  798.             LINESEG TempLineseg = *pCompiledLinesegs;
  799.             *pCompiledLinesegs = *pCompiledTree;
  800.             *pCompiledTree = TempLineseg;
  801.         }
  802.  
  803.         if (VisibleCompile)
  804.         {
  805.             EnableMenuItem(GetMenu (hwndApp), IDM_HALT_COMPILE,
  806.                            MF_GRAYED);
  807.             EnableMenuItem(GetMenu (hwndApp), IDM_EXIT, MF_GRAYED);
  808.             SetWindowText (hwndApp, "BSPMAKER - success - press a key");
  809.             DoStep = FALSE;
  810.             SingleStep = TRUE;  // so the message loop knows to let us
  811.                                 //  out on a keypress
  812.  
  813.             // Get messages until we can step
  814.             while (!DoStep) {
  815.                 MSG msg;
  816.  
  817.                 if (PeekMessage(&msg, 0, 0, 0, PM_REMOVE)) {
  818.                     TranslateMessage(&msg);
  819.                     DispatchMessage(&msg);
  820.                 }
  821.             }
  822.  
  823.             SingleStep = FALSE;
  824.             EnableMenuItem(GetMenu (hwndApp), IDM_EXIT, MF_ENABLED);
  825.             SetWindowText (hwndApp, "BSPMAKER");
  826.         }
  827.         else
  828.         {
  829.             DisplayMessageBox ("Successful compile");
  830.         }
  831.     }
  832.  
  833.     // Display the original line list
  834.     HDC hdc = GetDC(hwndApp);
  835.     AppPaint(hwndApp, hdc);
  836.     ReleaseDC(hwndApp, hdc);
  837.  
  838.     // Restore the normal menus
  839.     EnableMenuItem(GetMenu (hwndApp), IDM_LOAD, MF_ENABLED);
  840.     EnableMenuItem(GetMenu (hwndApp), IDM_COMPILE, MF_ENABLED);
  841.     EnableMenuItem(GetMenu (hwndApp), IDM_VISIBLE_COMPILE,
  842.                    MF_ENABLED);
  843.     EnableMenuItem(GetMenu (hwndApp), IDM_SINGLE_STEP_COMPILE,
  844.                    MF_ENABLED);
  845.     EnableMenuItem(GetMenu (hwndApp), IDM_HALT_COMPILE,
  846.                    MF_GRAYED);
  847.     EnableMenuItem(GetMenu (hwndApp), IDM_SAVE, MF_ENABLED);
  848.  
  849.     Compiling = FALSE;
  850. }
  851.  
  852.  
  853. /////////////////////////////////////////////////////////////////////
  854. // Builds a BSP tree from the specified line list. List must contain
  855. // at least one entry. If pCurrentTree is NULL, then this is the root
  856. // node, otherwise pCurrentTree is the tree that's been build so far.
  857. // Returns NULL for errors.
  858. /////////////////////////////////////////////////////////////////////
  859.  
  860. LINESEG * SelectBSPTree(LINESEG * plineseghead,
  861.     LINESEG * pCurrentTree, LINESEG ** pParentsChildPointer)
  862. {
  863.     LINESEG *pminsplit;
  864.     int minsplits;
  865.     int tempsplitcount;
  866.     LINESEG *prootline;
  867.     LINESEG *pcurrentline;
  868.     double nx, ny, numer, denom, t;
  869.  
  870. #if DBG
  871.     if (plineseghead == NULL) {
  872.         DisplayMessageBox("Empty line list passed to SelectBSPTree");
  873.         return NULL;
  874.     }
  875. #endif
  876.  
  877.     // Pick a line as the root, and remove it from the list of lines to be
  878.     // categorized. The line we'll select is the one of those in the list
  879.     // that splits the fewest of the other lines in the list
  880.     minsplits = MAX_INT;
  881.     prootline = plineseghead;
  882.  
  883.     while (prootline != NULL) {
  884.         pcurrentline = plineseghead;
  885.         tempsplitcount = 0;
  886.  
  887.         while (pcurrentline != NULL) {
  888.  
  889.             // See how many other lines the current line splits
  890.             nx = pvertexlist[prootline->startvertex].y -
  891.                     pvertexlist[prootline->endvertex].y;
  892.             ny = -(pvertexlist[prootline->startvertex].x -
  893.                     pvertexlist[prootline->endvertex].x);
  894.  
  895.             // Calculate the dot products we'll need for line intersection
  896.             // and spatial relationship
  897.             numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
  898.                     pvertexlist[prootline->startvertex].x)) +
  899.                     (ny * (pvertexlist[pcurrentline->startvertex].y -
  900.                     pvertexlist[prootline->startvertex].y));
  901.             denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
  902.                     pvertexlist[pcurrentline->startvertex].x)) +
  903.                     ((-ny) * (pvertexlist[pcurrentline->endvertex].y -
  904.                     pvertexlist[pcurrentline->startvertex].y));
  905.  
  906.             // Figure out if the infinite lines of the current line and the root
  907.             // intersect; if so, figure out if the current line segment is
  908.             // actually split, split if so, and add front/back polygons as
  909.             // appropriate
  910.             if (denom == 0.0) {
  911.  
  912.                 // No intersection, because lines are parallel; no split,
  913.                 // so nothing to do
  914.  
  915.             } else {
  916.  
  917.                 // Infinite lines intersect; figure out whether the actual line segment intersects the infinite line
  918.                 // of the root, and split if so
  919.                 t =  numer / denom;
  920.  
  921.                 if ((t > pcurrentline->tstart) &&
  922.                         (t < pcurrentline->tend)) {
  923.                     // The root splits the current line
  924.                     tempsplitcount++;
  925.                 } else {
  926.                     // Intersection outside segment limits, so no split,
  927.                     // nothing to do
  928.                 }
  929.             }
  930.  
  931.             pcurrentline = pcurrentline->pnextlineseg;
  932.         }
  933.  
  934.         if (tempsplitcount < minsplits) {
  935.             pminsplit = prootline;
  936.             minsplits = tempsplitcount;
  937.         }
  938.  
  939.         prootline = prootline->pnextlineseg;
  940.     }
  941.  
  942.     // For now, make this a leaf node so we can traverse the tree
  943.     // as it is at this point. BuildBSPTree() will add children as
  944.     // appropriate
  945.     pminsplit->pfronttree = NULL;
  946.     pminsplit->pbacktree = NULL;
  947.  
  948.     // Point the parent's child pointer to this node, so we can
  949.     // track the currently-build tree
  950.     *pParentsChildPointer = pminsplit;
  951.  
  952.     // Show the current state of building the BSP tree, if desired
  953.     if (VisibleCompile) {
  954.         if (!ShowSingleStepTree(plineseghead, pminsplit,
  955.                                 pCurrentTree)) {
  956.             return NULL;
  957.         }
  958.     }
  959.  
  960.     return BuildBSPTree(plineseghead, pminsplit, pCurrentTree);
  961. }
  962.  
  963.  
  964. /////////////////////////////////////////////////////////////////////
  965. // Builds a BSP tree given the specified root, by creating front and back
  966. // lists from the remaining lines, then calling itself recursively
  967. /////////////////////////////////////////////////////////////////////
  968.  
  969. LINESEG * BuildBSPTree(LINESEG * plineseghead, LINESEG * prootline,
  970.     LINESEG * pCurrentTree)
  971. {
  972.     LINESEG *pfrontlines;
  973.     LINESEG *pbacklines;
  974.     LINESEG *pcurrentline;
  975.     LINESEG *pnextlineseg;
  976.     LINESEG *psplitline;
  977.     double nx, ny, numer, denom, t;
  978.     int Done;
  979.  
  980.     //
  981.     // Categorize all non-root lines as either in front of the
  982.     // root's infinite line, behind the root's infinite line, or split by
  983.     // the root's infinite line, in which case we split it into two lines
  984.     //
  985.     pfrontlines = NULL;
  986.     pbacklines = NULL;
  987.  
  988.     pcurrentline = plineseghead;
  989.  
  990.     while (pcurrentline != NULL)
  991.     {
  992.       CHECK_FOR_BACKLINKS(pfrontlines);
  993.       CHECK_FOR_BACKLINKS(pbacklines);
  994.  
  995.       //
  996.       // Skip the root line when encountered
  997.       //
  998.       if (pcurrentline == prootline) {
  999.           pcurrentline = pcurrentline->pnextlineseg;
  1000.       } else  {
  1001.         nx = pvertexlist[prootline->startvertex].y -
  1002.                 pvertexlist[prootline->endvertex].y;
  1003.         ny = -(pvertexlist[prootline->startvertex].x -
  1004.                 pvertexlist[prootline->endvertex].x);
  1005.  
  1006.         //
  1007.         // Calculate the dot products we'll need for line intersection and
  1008.         // spatial relationship
  1009.         //
  1010.         numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
  1011.                  pvertexlist[prootline->startvertex].x)) +
  1012.                 (ny * (pvertexlist[pcurrentline->startvertex].y -
  1013.                  pvertexlist[prootline->startvertex].y));
  1014.         denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
  1015.                  pvertexlist[pcurrentline->startvertex].x)) +
  1016.                 (-(ny) * (pvertexlist[pcurrentline->endvertex].y -
  1017.                  pvertexlist[pcurrentline->startvertex].y));
  1018.  
  1019.         //
  1020.         // Figure out if the infinite lines of the current line and the root
  1021.         // intersect; if so, figure out if the current line segment is
  1022.         // actually split, split if so, and add front/back polygons as
  1023.         // appropriate
  1024.         //
  1025.         if (denom == 0.0) {
  1026.             //
  1027.             // No intersection, because lines are parallel; just add to
  1028.             // appropriate list
  1029.             //
  1030.             pnextlineseg = pcurrentline->pnextlineseg;
  1031.  
  1032.             if (numer < 0.0) {
  1033.  
  1034.                 // Current line is in front of root line; link into
  1035.                 // front list
  1036.                 pcurrentline->pnextlineseg = pfrontlines;
  1037.                 pfrontlines = pcurrentline;
  1038.  
  1039.             } else {
  1040.  
  1041.                 // Current line is behind root line; link into back list
  1042.                 pcurrentline->pnextlineseg = pbacklines;
  1043.                 pbacklines = pcurrentline;
  1044.  
  1045.             }
  1046.  
  1047.             pcurrentline = pnextlineseg;
  1048.  
  1049.         } else {
  1050.  
  1051.             // Infinite lines intersect; figure out whether the actual line
  1052.             // segment intersects the infinite line of the root, and split
  1053.             // if so
  1054.             t =  numer / denom;
  1055.  
  1056.             if ((t > pcurrentline->tstart) &&
  1057.                 (t < pcurrentline->tend)) {
  1058.  
  1059.                 // The line segment must be split; add one split segment to
  1060.                 // each list
  1061.                 if (NumCompiledLinesegs > (MAX_NUM_LINESEGS - 1)) {
  1062.                     DisplayMessageBox("Out of space for line segments; "
  1063.                                  "increase MAX_NUM_LINESEGS");
  1064.                     return NULL;
  1065.  
  1066.                 }
  1067.  
  1068.                 // Make a new line entry for the split part of the line
  1069.                 psplitline = &pCompiledLinesegs[NumCompiledLinesegs];
  1070.                 NumCompiledLinesegs++;
  1071.  
  1072.                 *psplitline = *pcurrentline;
  1073.                 psplitline->tstart = t;
  1074.                 pcurrentline->tend = t;
  1075.                 
  1076.                 pnextlineseg = pcurrentline->pnextlineseg;
  1077.  
  1078.                 if (numer < 0.0) {
  1079.  
  1080.                     // Presplit part is in front of root line; link
  1081.                     // into front list and put postsplit part in back
  1082.                     // list
  1083.                     pcurrentline->pnextlineseg = pfrontlines;
  1084.                     pfrontlines = pcurrentline;
  1085.  
  1086.                     psplitline->pnextlineseg = pbacklines;
  1087.                     pbacklines = psplitline;
  1088.  
  1089.                 } else {
  1090.  
  1091.                     // Presplit part is in back of root line; link
  1092.                     // into back list and put postsplit part in front
  1093.                     // list
  1094.                     psplitline->pnextlineseg = pfrontlines;
  1095.                     pfrontlines = psplitline;
  1096.  
  1097.                     pcurrentline->pnextlineseg = pbacklines;
  1098.                     pbacklines = pcurrentline;
  1099.  
  1100.                 }
  1101.  
  1102.                 pcurrentline = pnextlineseg;
  1103.  
  1104.             } else {
  1105.  
  1106.                 // Intersection outside segment limits, so no need to split;
  1107.                 // just add to proper list
  1108.                 pnextlineseg = pcurrentline->pnextlineseg;
  1109.  
  1110.                 Done = 0;
  1111.                 while (!Done) {
  1112.  
  1113.                     if (numer < -MATCH_TOLERANCE) {
  1114.  
  1115.                         // Current line is in front of root line;
  1116.                         // link into front list
  1117.                         pcurrentline->pnextlineseg = pfrontlines;
  1118.                         pfrontlines = pcurrentline;
  1119.                         Done = 1;
  1120.  
  1121.                     } else if (numer > MATCH_TOLERANCE) {
  1122.  
  1123.                         // Current line is behind root line; link into back list
  1124.                         pcurrentline->pnextlineseg = pbacklines;
  1125.                         pbacklines = pcurrentline;
  1126.                         Done = 1;
  1127.  
  1128.                     } else {
  1129.  
  1130.                         // The point on the current line we picked to do front/back
  1131.                         // evaluation happens to be collinear with the root, so use
  1132.                         // the other end of the current line and try again
  1133.                         numer = (nx * (pvertexlist[pcurrentline->endvertex].x -
  1134.                                  pvertexlist[prootline->startvertex].x)) +
  1135.                                 (ny * (pvertexlist[pcurrentline->endvertex].y -
  1136.                                  pvertexlist[prootline->startvertex].y));
  1137.                     }
  1138.                 }
  1139.  
  1140.                 pcurrentline = pnextlineseg;
  1141.             }
  1142.         }
  1143.       }
  1144.     }
  1145.  
  1146.     CHECK_FOR_BACKLINKS(pfrontlines);
  1147.     CHECK_FOR_BACKLINKS(pbacklines);
  1148.  
  1149.     // Make a node out of the root line, with the front and back trees
  1150.     // attached
  1151.     if (pfrontlines == NULL) {
  1152.         prootline->pfronttree = NULL;
  1153.     } else {
  1154.         if (!SelectBSPTree(pfrontlines, pCurrentTree,
  1155.                           &prootline->pfronttree)) {
  1156.             return NULL;
  1157.         }
  1158.     }
  1159.  
  1160.     if (pbacklines == NULL) {
  1161.         prootline->pbacktree = NULL;
  1162.     } else {
  1163.         if (!SelectBSPTree(pbacklines, pCurrentTree,
  1164.                           &prootline->pbacktree)) {
  1165.             return NULL;
  1166.         }
  1167.     }
  1168.  
  1169.     return(prootline);
  1170. }
  1171.  
  1172.  
  1173. #if DBG
  1174.  
  1175. /////////////////////////////////////////////////////////////////////
  1176. // Finds any backlinks (these are always errors) in the line segment
  1177. // list.
  1178. /////////////////////////////////////////////////////////////////////
  1179.  
  1180. void CheckForBacklinks(LINESEG *plineseg)
  1181. {
  1182.     LINESEG *p1,*p2;
  1183.  
  1184.     if ((plineseg == NULL) || (plineseg->pnextlineseg == NULL))
  1185.     {
  1186.         return;
  1187.     }
  1188.  
  1189.     p1 = plineseg;
  1190.     p2 = plineseg->pnextlineseg;
  1191.  
  1192.     while ((p1 != NULL) && (p2 != NULL))
  1193.     {
  1194.         if (p1 == p2)
  1195.         {
  1196.             DisplayMessageBox("Backlink");
  1197.             return;
  1198.         }
  1199.         p1 = p1->pnextlineseg;
  1200.         p2 = p2->pnextlineseg;
  1201.         if (p2 == NULL)
  1202.         {
  1203.             return;
  1204.         }
  1205.         p2 = p2->pnextlineseg;
  1206.     }
  1207. }
  1208. #endif    //DBG
  1209.  
  1210.  
  1211. /////////////////////////////////////////////////////////////////////
  1212. // Shows the current splitting line in the tree. Returns TRUE for
  1213. // success, FALSE for failure.
  1214. /////////////////////////////////////////////////////////////////////
  1215.  
  1216. int ShowSingleStepTree(LINESEG * pLinesegsToPartition,
  1217.     LINESEG * pSplit, LINESEG * pCurrentTree)
  1218. {
  1219.     HPEN hpen, hpenOld;
  1220.     POINT pt;
  1221.     SIZE size;
  1222.     HDC hdc;
  1223.     double StartX, StartY, EndX, EndY;
  1224.     LINESEG *pTemp;
  1225.  
  1226.     hdc = GetDC(hwndApp);
  1227.  
  1228.     PatBlt(hdcDraw, 0, 0, Width, Height, WHITENESS);
  1229.  
  1230.     SetMapMode(hdcDraw, MM_ANISOTROPIC);    
  1231.     SetWindowExtEx(hdcDraw, lineListMaxX - lineListMinX + 1,
  1232.                    lineListMaxY - lineListMinY + 1, &size);
  1233.     SetViewportExtEx(hdcDraw, Width*9/10, -Height*9/10, &size);
  1234.     SetViewportOrgEx(hdcDraw, Width/20, Height*19/20, &pt);
  1235.     SetWindowOrgEx(hdcDraw, lineListMinX, lineListMinY, &pt);
  1236.  
  1237.     // First, draw all the lines there are, in black
  1238.     hpenOld = SelectObject(hdcDraw, GetStockObject(BLACK_PEN));
  1239.  
  1240.     pTemp = pCompiledLinesegs;
  1241.     for (int i=0; i < NumCompiledLinesegs; i++, pTemp++) {
  1242.  
  1243.         StartX = pvertexlist[pTemp->startvertex].x;
  1244.         StartY = pvertexlist[pTemp->startvertex].y;
  1245.         EndX = pvertexlist[pTemp->endvertex].x;
  1246.         EndY = pvertexlist[pTemp->endvertex].y;
  1247.  
  1248.         MoveToEx(hdcDraw,
  1249.           (int)floor(StartX + (EndX - StartX) * pTemp->tstart + 0.5),
  1250.           (int)floor(StartY + (EndY - StartY) * pTemp->tstart + 0.5),
  1251.           &pt);
  1252.         LineTo(hdcDraw,
  1253.           (int)floor(StartX + (EndX - StartX) * pTemp->tend + 0.5),
  1254.           (int)floor(StartY + (EndY - StartY) * pTemp->tend + 0.5));
  1255.     }
  1256.  
  1257.     // Draw the lines being partitioned, in red
  1258.     hpen = CreatePen(PS_SOLID, 0, RGB(0xFF, 0x00, 0x00));
  1259.     DeleteObject(SelectObject(hdcDraw, hpen));
  1260.     pTemp = pLinesegsToPartition;
  1261.     while (pTemp) {
  1262.     
  1263.         StartX = pvertexlist[pTemp->startvertex].x;
  1264.         StartY = pvertexlist[pTemp->startvertex].y;
  1265.         EndX = pvertexlist[pTemp->endvertex].x;
  1266.         EndY = pvertexlist[pTemp->endvertex].y;
  1267.  
  1268.         MoveToEx(hdcDraw,
  1269.           (int)floor(StartX + (EndX - StartX) * pTemp->tstart + 0.5),
  1270.           (int)floor(StartY + (EndY - StartY) * pTemp->tstart + 0.5),
  1271.           &pt);
  1272.         LineTo(hdcDraw,
  1273.           (int)floor(StartX + (EndX - StartX) * pTemp->tend + 0.5),
  1274.           (int)floor(StartY + (EndY - StartY) * pTemp->tend + 0.5));
  1275.  
  1276.         pTemp = pTemp->pnextlineseg;
  1277.     }
  1278.  
  1279.     // Draw the line segment we're splitting along in cyan, and
  1280.     // make it fat
  1281.     hpen = CreatePen(PS_SOLID, 10, RGB(0x00, 0xFF, 0xFF));
  1282.     DeleteObject(SelectObject(hdcDraw, hpen));
  1283.  
  1284.     StartX = pvertexlist[pSplit->startvertex].x;
  1285.     StartY = pvertexlist[pSplit->startvertex].y;
  1286.     EndX = pvertexlist[pSplit->endvertex].x;
  1287.     EndY = pvertexlist[pSplit->endvertex].y;
  1288.  
  1289.     MoveToEx(hdcDraw,
  1290.             (int)floor(StartX + (EndX - StartX) *
  1291.                 pSplit->tstart + 0.5),
  1292.             (int)floor(StartY + (EndY - StartY) *
  1293.                 pSplit->tstart + 0.5),
  1294.             &pt);
  1295.     LineTo(hdcDraw,
  1296.             (int)floor(StartX + (EndX - StartX) * pSplit->tend + 0.5),
  1297.             (int)floor(StartY + (EndY - StartY) *
  1298.                 pSplit->tend + 0.5));
  1299.  
  1300.     // Walk the current tree and draw in dotted gray the full
  1301.     // spanning length of all lines currently in it, so the way the
  1302.     // tree carves up the world is visible
  1303.     hpen = CreatePen(PS_DOT, 0, RGB(0xC0, 0xC0, 0xC0));
  1304.     DeleteObject(SelectObject(hdcDraw, hpen));
  1305.  
  1306.     DrawAllSplitters(pCurrentTree, pCurrentTree);
  1307.  
  1308.     // Draw the lines already in the tree, in white to erase anything
  1309.     // that's already there, then in dotted green
  1310.     hpen = CreatePen(PS_SOLID, 0, RGB(0xFF, 0xFF, 0xFF));
  1311.     DeleteObject(SelectObject(hdcDraw, hpen));
  1312.     DisplayTree(pCurrentTree);
  1313.     hpen = CreatePen(PS_DOT, 0, RGB(0x00, 0xFF, 0x00));
  1314.     DeleteObject(SelectObject(hdcDraw, hpen));
  1315.     DisplayTree(pCurrentTree);
  1316.  
  1317.     // Draw the whole splitting line, spanning the area being split,
  1318.     // in dotted black
  1319.     hpen = CreatePen(PS_DOT, 0, RGB(0x00, 0x00, 0x00));
  1320.     DeleteObject(SelectObject(hdcDraw, hpen));
  1321.  
  1322.     DrawBSPClippedLine(pSplit, pCurrentTree);
  1323.  
  1324.     DeleteObject(SelectObject(hdcDraw, hpenOld));
  1325.  
  1326.     SetWindowExtEx(hdcDraw, Width, Height, &size);
  1327.     SetViewportExtEx(hdcDraw, Width, Height, &size);
  1328.     SetViewportOrgEx(hdcDraw, 0, 0, &pt);
  1329.     SetWindowOrgEx(hdcDraw, 0, 0, &pt);
  1330.     SetMapMode(hdcDraw, MM_TEXT);    
  1331.  
  1332.     BitBlt(hdc, 0, 0, Width, Height, hdcDraw, 0, 0, SRCCOPY);
  1333.  
  1334.     ReleaseDC(hwndApp, hdc);
  1335.     
  1336.     GdiFlush(); // make sure this gets drawn right away
  1337.  
  1338.     // When single-stepping, we have to wait for the message loop to
  1339.     // detect a keypress and set DoStep to TRUE. DoStep is always
  1340.     // left TRUE except for this case, so non-single-stepping
  1341.     // operation will only cause the loop below to repeat until the
  1342.     // message queue is cleared
  1343.     if (SingleStep) {
  1344.         DoStep = FALSE;
  1345.     }
  1346.  
  1347.     MSG msg;
  1348.  
  1349.     // Get messages until we can step
  1350.     while (!DoStep) {
  1351.         if (PeekMessage(&msg, 0, 0, 0, PM_REMOVE)) {
  1352.             TranslateMessage(&msg);
  1353.             DispatchMessage(&msg);
  1354.  
  1355.             // If this message caused the exit flag to be set, done
  1356.             if (HaltCompile) {
  1357.                 DoStep = TRUE;
  1358.                 return FALSE;
  1359.             }
  1360.         }
  1361.     }
  1362.     return TRUE;
  1363. }
  1364.  
  1365.  
  1366. /////////////////////////////////////////////////////////////////////
  1367. // Draws the line segments for all nodes in the current tree by
  1368. // calling itself recursively. Pen should be set on entry.
  1369. /////////////////////////////////////////////////////////////////////
  1370.  
  1371. void DisplayTree(LINESEG * pCurrentNode)
  1372. {
  1373.     double StartX, StartY, EndX, EndY;
  1374.     POINT pt;
  1375.  
  1376.     StartX = pvertexlist[pCurrentNode->startvertex].x;
  1377.     StartY = pvertexlist[pCurrentNode->startvertex].y;
  1378.     EndX = pvertexlist[pCurrentNode->endvertex].x;
  1379.     EndY = pvertexlist[pCurrentNode->endvertex].y;
  1380.  
  1381.     MoveToEx(hdcDraw,
  1382.         (int)floor(StartX +
  1383.          (EndX - StartX) * pCurrentNode->tstart + 0.5),
  1384.         (int)floor(StartY +
  1385.          (EndY - StartY) * pCurrentNode->tstart + 0.5),
  1386.         &pt);
  1387.     LineTo(hdcDraw,
  1388.         (int)floor(StartX +
  1389.          (EndX - StartX) * pCurrentNode->tend + 0.5),
  1390.         (int)floor(StartY +
  1391.          (EndY - StartY) * pCurrentNode->tend + 0.5));
  1392.  
  1393.     if (pCurrentNode->pfronttree) {
  1394.         DisplayTree(pCurrentNode->pfronttree);
  1395.     }
  1396.  
  1397.     if (pCurrentNode->pbacktree) {
  1398.         DisplayTree(pCurrentNode->pbacktree);
  1399.     }
  1400. }
  1401.  
  1402.  
  1403. /////////////////////////////////////////////////////////////////////
  1404. // Draws the whole line for lineseg pSplit, clipped to the area of
  1405. // pCurrentTree that pSplit is in. Pen should be set on entry.
  1406. /////////////////////////////////////////////////////////////////////
  1407.  
  1408. void DrawBSPClippedLine(LINESEG *pSplit, LINESEG *pCurrentTree)
  1409. {
  1410.     double StartX, StartY, EndX, EndY;
  1411.     double ClippedTStart, ClippedTEnd;
  1412.     double LinesegTStart, LinesegTEnd;
  1413.     double nx, ny, numer, denom, t;
  1414.     LINESEG *pCurrentNode;
  1415.     POINT pt;
  1416.  
  1417.     StartX = pvertexlist[pSplit->startvertex].x;
  1418.     StartY = pvertexlist[pSplit->startvertex].y;
  1419.     EndX = pvertexlist[pSplit->endvertex].x;
  1420.     EndY = pvertexlist[pSplit->endvertex].y;
  1421.     LinesegTStart = pSplit->tstart;
  1422.     LinesegTEnd = pSplit->tend;
  1423.  
  1424.     // Make the line longer than any line can be, so we don't miss
  1425.     // anything as we clip it
  1426.     ClippedTStart = -1000000.0;
  1427.     ClippedTEnd = 1000000.0;
  1428.  
  1429.     // Clip the line to the tree, keeping what's on the same side as
  1430.     // the pSplit lineseg and descending in that direction. Stop if
  1431.     // we get to a node that's the pSplit lineseg; that means we've
  1432.     // done all the clipping there is to do
  1433.     pCurrentNode = pCurrentTree;
  1434.     while ((pCurrentNode != pSplit) && (pCurrentNode != NULL)) {
  1435.  
  1436.         nx = pvertexlist[pCurrentNode->startvertex].y -
  1437.                 pvertexlist[pCurrentNode->endvertex].y;
  1438.         ny = -(pvertexlist[pCurrentNode->startvertex].x -
  1439.                 pvertexlist[pCurrentNode->endvertex].x);
  1440.  
  1441.         // Calculate the dot products we'll need for line
  1442.         // intersection and spatial relationship
  1443.  
  1444.         //*** can just store the pSplit values once for this***
  1445.  
  1446.         numer = (nx * (pvertexlist[pSplit->startvertex].x -
  1447.                  pvertexlist[pCurrentNode->startvertex].x)) +
  1448.                 (ny * (pvertexlist[pSplit->startvertex].y -
  1449.                  pvertexlist[pCurrentNode->startvertex].y));
  1450.         denom = ((-nx) * (pvertexlist[pSplit->endvertex].x -
  1451.                  pvertexlist[pSplit->startvertex].x)) +
  1452.                 ((-ny) * (pvertexlist[pSplit->endvertex].y -
  1453.                  pvertexlist[pSplit->startvertex].y));
  1454.  
  1455.         // Figure out if the infinite lines of the current line and
  1456.         // the root intersect; if so, figure out if the current line
  1457.         // segment is actually split, split if so, and add front/back
  1458.         // polygons as appropriate
  1459.         if (denom == 0.0) {
  1460.             // No intersection, because lines are parallel; no need
  1461.             // to do anything except descend in the right direction
  1462.             if (numer < 0.0) {
  1463.  
  1464.                 // Splitting line is in front of this clip line, so
  1465.                 // descend to front
  1466.                 pCurrentNode = pCurrentNode->pfronttree;
  1467.  
  1468.             } else {
  1469.  
  1470.                 // Splitting line is behind this clip line, so descend
  1471.                 // to back
  1472.                 pCurrentNode = pCurrentNode->pbacktree;
  1473.  
  1474.             }
  1475.  
  1476.         } else {
  1477.  
  1478.             // Infinite lines intersect; figure out whether the
  1479.             // infinite clipping line intersects the actual splitting
  1480.             // line segment, and clip if so
  1481.             t =  numer / denom;
  1482.  
  1483.             if ((t > ClippedTStart) && (t < ClippedTEnd)) {
  1484.  
  1485.                 // The tree can't clip the actual lineseg (which has
  1486.                 // already been clipped to the tree), so a single
  1487.                 // comparison tells us which end of the splitting
  1488.                 // line just got clipped
  1489.                 if (t <= LinesegTStart) {
  1490.                     ClippedTStart = t;
  1491.                 } else {
  1492.                     ClippedTEnd = t;
  1493.                 }
  1494.  
  1495.             }
  1496.  
  1497.             // Walk to the child tree on the side that the
  1498.             // remaining part of the splitting line is on
  1499.             int Done = FALSE;
  1500.  
  1501.             // Recalculate based on the actual endpoints of the
  1502.             // line segment for which we're clipping the infinite
  1503.             // line, because we're sure that both line segment
  1504.             // endpoints are already fully clipped to the tree
  1505.             double FullyClippedX = StartX +
  1506.                     (EndX - StartX) * LinesegTStart;
  1507.             double FullyClippedY = StartY +
  1508.                     (EndY - StartY) * LinesegTStart;
  1509.  
  1510.             do {
  1511.  
  1512.                 numer = (nx * (FullyClippedX -
  1513.                         pvertexlist[pCurrentNode->startvertex].x)) +
  1514.                         (ny * (FullyClippedY -
  1515.                         pvertexlist[pCurrentNode->startvertex].y));
  1516.  
  1517.                 if (numer < -MATCH_TOLERANCE) {
  1518.  
  1519.                     pCurrentNode = pCurrentNode->pfronttree;
  1520.                     Done = TRUE;
  1521.  
  1522.                 } else if (numer > MATCH_TOLERANCE) {
  1523.  
  1524.                     pCurrentNode = pCurrentNode->pbacktree;
  1525.                     Done = TRUE;
  1526.  
  1527.                 } else {
  1528.                 
  1529.                     // The point on the splitting line we picked to do
  1530.                     // front/back evaluation happens to be collinear with
  1531.                     // the current clipping line, so use the other end of
  1532.                     // the splitting line and try again
  1533.                     FullyClippedX = StartX +
  1534.                             (EndX - StartX) * LinesegTEnd;
  1535.                     FullyClippedY = StartY +
  1536.                             (EndY - StartY) * LinesegTEnd;
  1537.                 }
  1538.             } while (!Done);
  1539.         }
  1540.     }
  1541.  
  1542.     // Draw the splitting line across the area it splits
  1543.     if ((ClippedTStart != 1000000.0) && (ClippedTEnd != 1000000.0)) {
  1544.         MoveToEx(hdcDraw,
  1545.              (int)floor(StartX +
  1546.               (EndX - StartX) * ClippedTStart + 0.5),
  1547.              (int)floor(StartY +
  1548.               (EndY - StartY) * ClippedTStart + 0.5),
  1549.             &pt);
  1550.         LineTo(hdcDraw,
  1551.            (int)floor(StartX + (EndX - StartX) * ClippedTEnd + 0.5),
  1552.            (int)floor(StartY + (EndY - StartY) * ClippedTEnd + 0.5));
  1553.     }
  1554. }
  1555.  
  1556.  
  1557. /////////////////////////////////////////////////////////////////////
  1558. // Draws all splitting lines in the tree pTree starting at
  1559. // pCurrentSplitter, each clipped by the higher levels of the tree.
  1560. /////////////////////////////////////////////////////////////////////
  1561.  
  1562. void DrawAllSplitters(LINESEG *pCurrentSplitter, LINESEG * pTree)
  1563. {
  1564.     DrawBSPClippedLine(pCurrentSplitter, pTree);
  1565.     if (pCurrentSplitter->pfronttree) {
  1566.         DrawAllSplitters(pCurrentSplitter->pfronttree, pTree);
  1567.     }
  1568.     if (pCurrentSplitter->pbacktree) {
  1569.         DrawAllSplitters(pCurrentSplitter->pbacktree, pTree);
  1570.     }
  1571. }
  1572.